package ljl.alg.jianzhioffer.round2;

/**
 * 某个数字出现一次
 * 其它数字都出现了三次
 */
public class _56_2_single_number {
    
    
    /**
     * 我思路是，如果从每一位开始看的话，出现奇数次的位需要被干掉
     * 剩下的位拼起来就是那个数字
     * 开整！
     * <p>
     * 做出来了，不快就是
     */
    public int singleNumber888(int[] nums) {
        int[] bits = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                if ((num & 1) == 1) {
                    bits[i]++;
                }
                num >>= 1;
            }
        }
        
        int mask = 1;
        int res = 0;
        for (int i = 0; i < 32; i++) {
            if ((bits[i] % 3 != 0)) {
                res |= mask;
            }
            mask <<= 1;
        }
        
        // 还有一种写法，这个写法只需要一个变量，上面不是需要两个吗
        /*
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res <<= 1;
            res |= bits[32 - i] % 3;
        }
        */
        
        return res;
    }
    
    /*
     * 每一位，最终回到 3 的倍数，
     * 单崩个那个数，会让它变成不是 3 的倍数
     *
     * 搞三个状态
     * 00 01 10，会不停在三个状态流转
     * 因为一位只能表示一个数，想表示两个数得需要两个变量，设为
     * two one
     *
     * 碰到 0 状态不变，所以只看碰到 1 的
     *
     * 状态变化为
     * 00 - 01
     * 01 - 10
     * 10 - 00
     *
     * 先看 one 的变化，one 变化时还受到 two 的影响，比如 two 已经是 1 了，one 是 0
     * 再碰到 1，one 和 two 都要归零，因为最多到 10，用公式来表示
     *
     * if two == 0
     *   if n == 0
     *     one = one
     *   if n == 1
     *     one = ~one
     * if two == 1
     *   one = 0
     *
     * 可以进一步化简为
     * if two == 0
     *   one = one ^ n
     * if two == 1
     *   one = 0
     *
     * 可以进一步化简为
     * one = one ^ n & ~two
     *
     * 下面要考虑 two 这一位
     * 这个考虑，虽说是完全一样，但我看了得有四个小时才整明白，或我自以为整明白了
     *
     * 抄一遍状态
     * 00 - 01
     * 01 - 10
     * 10 - 00
     *
     * 假设这两列两位数字，每一列分别为 1 2 3 4
     * 看 two 时，one 已经转移完了，所以，看第一列，也就是原始的 two
     * 和第四列，也就是转移之后的 one，最终结果是第三列，也就是转移之后的 two
     * if one == 1
     *   two = 0
     * if one == 0
     *   if n == 0
     *     two = two
     *   if n == 1
     *     two = ~two
     *
     * 这不正好是，一模一样
     *  */
    public int singleNumber(int[] nums) {
        int one = 0, two = 0;
        for (int num : nums) {
            one = one ^ num & ~two;
            two = two ^ num & ~one;
        }
        return one;
    }
}
